package com.linyaonan.leetcode.sword_to_offer._13;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 *
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 *
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    int count = 0;

    /**
     * 改题目类似于机器人走迷宫，使用全局的计数器来计数
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        int[][] pp = new int[m][n];
        move(0, 0, m - 1, n - 1, k, pp);
        return count;
    }

    public void move(int m, int n, int mMax, int nMax, int k, int[][] pp) {
        if (m < 0 || n < 0 || m > mMax || n > nMax  || pp[m][n] == 1) {
            return;
        } else {
            // 判断位数相加
            String[] s1 = String.valueOf(m).split("");
            String[] s2 = String.valueOf(n).split("");
            int pCount = 0;
            for (String s : s1) {
                if (pCount > k) {
                    return;
                }
                pCount += Integer.valueOf(s);
            }
            for (String s : s2) {
                if (pCount > k) {
                    return;
                }
                pCount += Integer.valueOf(s);
            }
            if (pCount <= k) {
                count++;
                pp[m][n] = 1;
                move(m - 1, n , mMax, nMax, k, pp);
                move(m, n - 1 , mMax, nMax, k, pp);
                move(m + 1, n , mMax, nMax, k, pp);
                move(m, n + 1 , mMax, nMax, k, pp);
            }
        }
    }
}